/* CANONICALISATION services for patterns

*/
#include "skfrtype.h"

#include "sk_gpat_can.h"
#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;

extern word trowperms[512][1296]; // table of all row possible perms
extern byte tcrossperms[64][72];
extern word tmax9[512]; // computed table max equivalent to a pattern for row1
extern word tperm6[6][3];
extern byte tmin3[8];
 // une table donnant les deux autres lignes / colonnes 
extern byte tothers_rc[18][2];
extern byte tothers_band [6][2];
extern byte t_units_per_band[6][3];
extern byte tpermsminir1[8][6];

// entry 18 rows cols patterns  trowperms[512][1296];
int highfib=0,highband=0,high2band=0;// debugging code

int CAN_ON_PATTERN::Canonical(word * pr_in,int check){

//	cout << "check one "<<endl;
	max_store1=n_store1=0;
	for(int i=0;i<18;i++) {
		word *pp=trowperms[pr_in[i]];
		for(int j=0;j<1296;j++){
			word w=pp[j];
			if(w>max_store1){ 
				if(check && (i || j)  ){
					if(check==2){
						cout << "one max i=" <<i << oct << "rx=" << pr_in[i]<< dec<< " j=" << j 
							<< "woct=" <<oct << w << dec << endl;
					}
					return 0; // source is not canonical
				}
				max_store1=w; 
				n_store1=0;
			}
			if(w==max_store1){
				t_fib[n_store1].rc=i;
				t_fib[n_store1++].perm=j;
			}
		}
	}
	
	if(n_store1>highfib){
		highfib=n_store1;
		if(highfib>2000) cerr<<"highfib ="<<highfib<<endl;
	}

//	cout << "check band n="<<n_store1 << endl;
	// restart from all possible ( row ) 1 and find max band 1
	max_band=n_band=0;
	for(int i=0;i<n_store1;i++){
		word rc=t_fib[i].rc,perm=t_fib[i].perm,band=rc/3;
		for(int j=0;j<2;j++){// 2 perms for other rows cols
			word r2 = tothers_rc[rc][j],
				 r3 = tothers_rc[rc][1-j],
				 vr2 = trowperms[pr_in[r2]][perm],
				 vr3 = trowperms[pr_in[r3]][perm];
			int w=(max_store1<<18)+(vr2<<9) + vr3;
			if(w>max_band){ 
				if(check && (band || perm)  ){
					if(check==2){
  						cout << "check band i=" <<i <<  "perm=" << perm<< dec<< " j=" << j 
						<< " r1="<<rc<<" r2="<<r2<< " r3=" << r3
						<< " permbloc="<< perm/216 << " permsolde=" << perm-216*(perm/216) 
						<< "  woct=" <<oct << w << dec << endl;
					}
					return 0; // source is not canonical
				}
				max_band=w; 
				n_band=0;
			}
			if(w==max_band){
				bs[n_band].band = band;
				bs[n_band++].perm = perm;
			}
		}
	}
	
	if(n_band>highband){
		highband=n_band;
		if(highband>2000) cerr<<"highband ="<<highband<<endl;
	}
	
	// restart from all max bande 1 and find all active bi band 
	max_2band = n_2band = 0;
	
	for(int i=0;i<n_band;i++){
		word band=bs[i].band,perm=bs[i].perm;
		for(int j=0;j<2;j++){// 2 possible band 2
			byte band2=tothers_band[band][j],
				* units=t_units_per_band[band2];
			// must try all perms on units 
			for(int ip=0;ip<6;ip++){
				word * pp=tperm6[ip];
				int w=( (trowperms[ pr_in [ units[pp[0]] ] ]  [perm])<<18) 
				    + ( trowperms[ pr_in [ units[pp[1]] ] ]  [perm]<<9)
				    +   trowperms[ pr_in [ units[pp[2]] ] ] [perm];
				if(w>max_2band){ 
					if(check && (i || j || ip )  ){
						if( check==2){
							cout << "check band2 i=" <<i <<  "perm=" << perm
								<< dec<< " j=" << j<< " ip=" << ip
								<< " r1="<<(int)units[pp[0]]<<" r2="<<(int)units[pp[1]]<< " r3=" <<(int) units[pp[2]]
								<< " permbloc="<< perm/216 << " permsolde=" << perm-216*(perm/216) 
								<< "  woct=" <<oct << w << dec << endl;
						}
						return 0; // source is not canonical
					}
					max_2band=w; 
					n_2band=0;
				}

				if(w==max_2band){
					bs2[n_2band].b3=tothers_band[band][1-j];
					bs2[n_2band++].perm=perm;
				}
			}
		}
	}
	if(n_2band>high2band){
		high2band=n_2band;
		if(high2band>100) cerr<<"high2band ="<<high2band<<endl;
	}


	// restart from all equivalent bi band to end
	max_3band=0;
	for(int i=0;i<n_2band;i++){
		word band3=bs2[i].b3,perm=bs2[i].perm;
		byte * units=t_units_per_band[band3];	
		// must try all perms on units 
		for(int ip=0;ip<6;ip++){
			word * pp=tperm6[ip];
			int w=( trowperms[ pr_in [ units[pp[0]] ] ]  [perm]<<18) 
			    + ( trowperms[ pr_in [ units[pp[1]] ] ]  [perm]<<9)
			    +   trowperms[ pr_in [ units[pp[2]] ] ]  [perm];
			if(w>max_3band){ 
					if(check==2){
						cout << "check third band failed  n_2band="<< n_2band << endl;
						cout << "check band3 i="<< dec  <<i <<  "perm=" << perm
								<< " ip=" << ip		<< " r1="<<(int)units[pp[0]]
								<<" r2="<<(int)units[pp[1]]<< " r3=" <<(int) units[pp[2]]
								<< " permbloc="<< perm/216 << " permsolde=" << perm-216*(perm/216) 
								<< "  b1=" <<oct <<max_band << "  b2=" <<oct <<max_2band 
								<< "  old=" <<oct <<max_3band << "  woct=" <<oct << w << dec << endl;
					}
				if(check && (i || ip )  ){
					return 0; // source is not canonical
				}
				max_3band=w; 
			}
		}
	}
	return 1;
}

void CAN_ON_PATTERN::Can_6rows(word * pr_in){

	max_store1=n_store1=0;
	for(int i=0;i<3;i++) { // look for max band1
		word *pp=trowperms[pr_in[i]];
		for(int j=0;j<1296;j++){
			word w=pp[j];
			if(w>max_store1){ 
				max_store1=w; 
				n_store1=0;
			}
			if(w==max_store1){
				t_fib[n_store1].rc=i;
				t_fib[n_store1++].perm=j;
			}
		}
	}

//	cout << "check band n="<<n_store1 << endl;
	// restart from all possible ( row ) 1 and find max band 1
	max_band=n_band=0;
	for(int i=0;i<n_store1;i++){
		word rc=t_fib[i].rc,perm=t_fib[i].perm,band=rc/3;
		for(int j=0;j<2;j++){// 2 perms for other rows cols
			word r2 = tothers_rc[rc][j],
				 r3 = tothers_rc[rc][1-j],
				 vr2 = trowperms[pr_in[r2]][perm],
				 vr3 = trowperms[pr_in[r3]][perm];
			int w=(max_store1<<18)+(vr2<<9) + vr3;
			if(w>max_band){ 
				max_band=w; 
				n_band=0;
			}
			if(w==max_band){
				bs[n_band].band = band;
				bs[n_band++].perm = perm;
			}
		}
	}
	
	// restart from all max bande 1 and find all active bi band 
	max_2band = n_2band = 0;
	
	for(int i=0;i<n_band;i++){
		word band=bs[i].band,perm=bs[i].perm;
		for(int j=0;j<2;j++){// 2 possible band 2
			byte band2=1,
				* units=t_units_per_band[band2];
			// must try all perms on units 
			for(int ip=0;ip<6;ip++){
				word * pp=tperm6[ip];
				int w=( (trowperms[ pr_in [ units[pp[0]] ] ]  [perm])<<18) 
				    + ( trowperms[ pr_in [ units[pp[1]] ] ]  [perm]<<9)
				    +   trowperms[ pr_in [ units[pp[2]] ] ] [perm];
				if(w>max_2band){ 
					max_2band=w; 
					n_2band=0;
				}

				if(w==max_2band){
					bs2[n_2band].b3=tothers_band[band][1-j];
					bs2[n_2band++].perm=perm;
				}
			}
		}
	}

}

int CAN_ON_PATTERN::CheckBand3(word * pr_in){
    // here band 1 is locked, band 2 must be canonical 
	// this is for a X Y 27 generation where X > Y comes first
	max_store1=n_store1=0;
	for(int i=0;i<3;i++) { // look for max band1
		word *pp=trowperms[pr_in[i]];
		for(int j=0;j<1296;j++){
			word w=pp[j];
			if(w>max_store1){ 
				max_store1=w; 
				n_store1=0;
			}
			if(w==max_store1){
				t_fib[n_store1].rc=i;
				t_fib[n_store1++].perm=j;
			}
		}
	}
//	cout << "check band n="<<n_store1 << endl;
	// restart from all possible ( row ) 1 and find max band 1
	max_band=n_band=0;
	for(int i=0;i<n_store1;i++){
		word rc=t_fib[i].rc,perm=t_fib[i].perm,band=0;
		for(int j=0;j<2;j++){// 2 perms for other rows cols
			word r2 = tothers_rc[rc][j],
				 r3 = tothers_rc[rc][1-j],
				 vr2 = trowperms[pr_in[r2]][perm],
				 vr3 = trowperms[pr_in[r3]][perm];
			int w=(max_store1<<18)+(vr2<<9) + vr3;
			if(w>max_band){ 
				max_band=w; 
				n_band=0;
			}
			if(w==max_band){
				bs[n_band].band = band;
				bs[n_band++].perm = perm;
			}
		}
	}	// find max2 band using perm 0 band 
	max_2band =  0;	
	
	for(int i=0;i<n_band;i++){
		word perm=bs[i].perm;
		byte * units=t_units_per_band[1];
		// must try all perms on units 
		for(int ip=0;ip<6;ip++){
			word * pp=tperm6[ip];
			int w=( (trowperms[ pr_in [ units[pp[0]] ] ]  [perm])<<18) 
		    + ( trowperms[ pr_in [ units[pp[1]] ] ]  [perm]<<9)
		    +   trowperms[ pr_in [ units[pp[2]] ] ] [perm];
			if(w>max_2band){ 
				if( ip || perm )return 0; // source is not canonical				
				max_2band=w; 
			}
		}
	}
	return 1;

}


int CAN_ON_PATTERN::CheckBands_2_3(word * pr_in){// pr_in is rows 4 to 9
	// this is specific to XY27 generation
	// as band 1 is full, just check maxlex bands2 3 
	max_store1=n_store1=0;
	for(int i=0;i<6;i++) {
		word *pp=trowperms[pr_in[i]];
		for(int j=0;j<1296;j++){
			word w=pp[j];
			if(w>max_store1){ 
				if(i || j  )	return 0; // source is not canonical
				max_store1=w; 
				n_store1=0;
			}
			if(w==max_store1){
				t_fib[n_store1].rc=i;
				t_fib[n_store1++].perm=j;
			}
		}
	}
	// restart from all possible ( row ) 1 and find max band 1
	max_band=n_band=0;
	for(int i=0;i<n_store1;i++){
		word rc=t_fib[i].rc,perm=t_fib[i].perm,band=rc/3;
		for(int j=0;j<2;j++){// 2 perms for other rows cols
			word r2 = tothers_rc[rc][j],
				 r3 = tothers_rc[rc][1-j],
				 vr2 = trowperms[pr_in[r2]][perm],
				 vr3 = trowperms[pr_in[r3]][perm];
			int w=(max_store1<<18)+(vr2<<9) + vr3;
			if(w>max_band){ 
				if(band || perm  )	return 0; // source is not canonical
				max_band=w; 
				n_band=0;
			}
			if(w==max_band){
				bs[n_band].band = band;
				bs[n_band++].perm = perm;
			}
		}
	}


	if(!(pr_in[3]+pr_in[4]+pr_in[5])) return 1; // it was a one band check
	// restart from all max bande 1 and find all active bi band 
	max_2band  = 0;
	for(int i=0;i<n_band;i++){
		word band=bs[i].band,perm=bs[i].perm;
		for(int j=0;j<2;j++){// 2 possible band 2
			byte band2=tothers_band[band][j],
				* units=t_units_per_band[band2];
			// must try all perms on units 
			for(int ip=0;ip<6;ip++){
				word * pp=tperm6[ip];
				int w=( (trowperms[ pr_in [ units[pp[0]] ] ]  [perm])<<18) 
				    + ( trowperms[ pr_in [ units[pp[1]] ] ]  [perm]<<9)
				    +   trowperms[ pr_in [ units[pp[2]] ] ] [perm];
				if(w>max_2band){ 
					if(i || j || ip   )return 0; // source is not canonical
					max_2band=w; 
				}
			}
		}
	}
	return 1;
}


int CAN_ON_PATTERN::MinLexBand40(word * pr_in){
	word min1v;
	int min27v;
	char min1 [10],min27[28],minw1[10],minw27[27];
	min1[9]=min27[27]=minw1[9]=minw27[27]=0;
	min1[0]=min27[0]='9'; // to force the first min

	// this is a crossing band, left box can not be changed
	FIRST_IN_BAND t_r[100];
	word minir=10,nr=0;	// look for starts in box 1 
	char cminir[4],cminirw[4];
	cminir[3]=cminirw[3]=0;
	cminir[0]='2';
	if(((pr_in[0] | pr_in[1]| pr_in[2]) & 07) ==0){ // keep it simple here
		t_r[0].perm=t_r[1].perm=t_r[2].perm=0;
		minir=0;
		nr=3;
		for(int i=0;i<3;i++) t_r[i].rc=i;
	}
	else{ // general case if not box1 empty
		for(int i=0;i<3;i++) { // look for min minirow box 1
			word mini0=pr_in[i]&7;// this is minlex
			byte *pp=tpermsminir1[mini0];
			for(int j=0;j<6;j++){ // perms on minirow first box
				word w=pp[j];
				// build the string
				for(int k=0;k<3;k++) 
					if(w & (1<<k)) cminirw[k]='1'; else cminirw[k]='.';
				int ir=strcmp(cminirw,cminir);
				if(ir<0){ // this is minlex left to right
					strcpy(cminir,cminirw);
					minir=w; 
					nr=0;
				}
				if(w==minir){
					t_r[nr].perm=j;
					t_r[nr++].rc =i;
				}
			}	
		}
	}
//	cout << "after box1 nr="<<nr<< " minir "<<minir << endl;
	// build now the row starts
	max_store1=07777;// here will be min, not max
	n_store1=0;  
	for(int i=0;i<nr;i++){ // all equivalent min in box 1
		word p3_8 = pr_in[t_r[i].rc] >>3; // boxes 2 3 minlex
		byte *pp=tcrossperms[p3_8];
		for(int j=0;j<72;j++){
			word w=(pp[j]<<3)+minir;
			// switch to string for minlex comparison
			for(int k=0;k<9;k++) 
				if(w & (1<<k)) minw1[k]='1'; else minw1[k]='.';
			int ir=strcmp(minw1,min1);
			if(ir<0){ 
				strcpy(min1,minw1); 
				min1v=w;
				n_store1=0;
			}
			if(ir==0){
				t_fib[n_store1].rc=t_r[i].rc;
				t_fib[n_store1++].perm=(j<<3) + t_r[i].perm;
			}
		}
	}
//	cout << "after first row n_store1=="<<n_store1<< " min1 " << min1<< endl;
	// build now the mini   restart from all possible ( row ) 1 and find band 1 (minlex)
	for(int i=0;i<n_store1;i++){
		word rc=t_fib[i].rc,
			 perm=t_fib[i].perm >>3,
			 perm0=t_fib[i].perm & 7;
		for(int j=0;j<2;j++){// 2 perms for other rows  
			word r2 =pr_in[ tothers_rc[rc][j] ],
				 r3 =pr_in[ tothers_rc[rc][1-j] ],	
				 xr2=tcrossperms[r2 >>3][perm],
				 xr3=tcrossperms[r3 >>3][perm],
				 yr2=tpermsminir1[r2&7][perm0],
				 yr3=tpermsminir1[r3&7][perm0],
				 vr2 =(xr2<<3)+yr2,
				 vr3 =(xr3<<3)+yr3;
			int w=(vr2<<9) + (vr3<<18);
			// build the string 
			strcpy (minw27,min1); 
			for(int k=9;k<27;k++) 
				if(w & (1<<k)) minw27[k]='1'; else minw27[k]='.';
			int ir=strcmp(minw27,min27);
			if(ir<0){
				strcpy(min27,minw27); 
				min27v=w+min1v;
			}
			
		}
	}
//	cout << "min band " <<   min27<<endl;
	return min27v;
}

//The original is published under the following license
		/***********************************************************************
		*               Original software is part of the ast package               *
		*          Copyright (c) 2005-2009 AT&T Intellectual Property          *
		*                      and is licensed under the                       *
		*                  Common Public License, Version 1.0                  *
		*                    by AT&T Intellectual Property                     *
		*                                                                      *
		*                A copy of the License is available at                 *
		*            http://www.opensource.org/licenses/cpl1.0.txt             *
		*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
		*                                                                      *
		*              Information and Software Systems Research               *
		*                            AT&T Research                             *
		*                           Florham Park NJ                            *
		*                                                                      *
		*                 Glenn Fowler <gsf@research.att.com>                  *
		***********************************************************************/
//This is a MODIFIED version of the original code 

byte	tswap[18][9][9] ={
	{
		{  0, 1, 2, 3, 4, 5, 6, 7, 8 },
		{  9,10,11,12,13,14,15,16,17 },
		{ 18,19,20,21,22,23,24,25,26 },
		{ 27,28,29,30,31,32,33,34,35 },
		{ 36,37,38,39,40,41,42,43,44 },
		{ 45,46,47,48,49,50,51,52,53 },
		{ 54,55,56,57,58,59,60,61,62 },
		{ 63,64,65,66,67,68,69,70,71 },
		{ 72,73,74,75,76,77,78,79,80 }
	},
	{
		{  3, 4, 5, 6, 7, 8, 0, 1, 2 },
		{ 12,13,14,15,16,17, 9,10,11 },
		{ 21,22,23,24,25,26,18,19,20 },
		{ 30,31,32,33,34,35,27,28,29 },
		{ 39,40,41,42,43,44,36,37,38 },
		{ 48,49,50,51,52,53,45,46,47 },
		{ 57,58,59,60,61,62,54,55,56 },
		{ 66,67,68,69,70,71,63,64,65 },
		{ 75,76,77,78,79,80,72,73,74 }
	},
	{
		{  6, 7, 8, 0, 1, 2, 3, 4, 5 },
		{ 15,16,17, 9,10,11,12,13,14 },
		{ 24,25,26,18,19,20,21,22,23 },
		{ 33,34,35,27,28,29,30,31,32 },
		{ 42,43,44,36,37,38,39,40,41 },
		{ 51,52,53,45,46,47,48,49,50 },
		{ 60,61,62,54,55,56,57,58,59 },
		{ 69,70,71,63,64,65,66,67,68 },
		{ 78,79,80,72,73,74,75,76,77 }
	},
	{
		{ 27,28,29,30,31,32,33,34,35 },
		{ 36,37,38,39,40,41,42,43,44 },
		{ 45,46,47,48,49,50,51,52,53 },
		{ 54,55,56,57,58,59,60,61,62 },
		{ 63,64,65,66,67,68,69,70,71 },
		{ 72,73,74,75,76,77,78,79,80 },
		{  0, 1, 2, 3, 4, 5, 6, 7, 8 },
		{  9,10,11,12,13,14,15,16,17 },
		{ 18,19,20,21,22,23,24,25,26 }
	},
	{
		{ 30,31,32,33,34,35,27,28,29 },
		{ 39,40,41,42,43,44,36,37,38 },
		{ 48,49,50,51,52,53,45,46,47 },
		{ 57,58,59,60,61,62,54,55,56 },
		{ 66,67,68,69,70,71,63,64,65 },
		{ 75,76,77,78,79,80,72,73,74 },
		{  3, 4, 5, 6, 7, 8, 0, 1, 2 },
		{ 12,13,14,15,16,17, 9,10,11 },
		{ 21,22,23,24,25,26,18,19,20 }
	},
	{
		{ 33,34,35,27,28,29,30,31,32 },
		{ 42,43,44,36,37,38,39,40,41 },
		{ 51,52,53,45,46,47,48,49,50 },
		{ 60,61,62,54,55,56,57,58,59 },
		{ 69,70,71,63,64,65,66,67,68 },
		{ 78,79,80,72,73,74,75,76,77 },
		{  6, 7, 8, 0, 1, 2, 3, 4, 5 },
		{ 15,16,17, 9,10,11,12,13,14 },
		{ 24,25,26,18,19,20,21,22,23 }
	},
	{
		{ 54,55,56,57,58,59,60,61,62 },
		{ 63,64,65,66,67,68,69,70,71 },
		{ 72,73,74,75,76,77,78,79,80 },
		{  0, 1, 2, 3, 4, 5, 6, 7, 8 },
		{  9,10,11,12,13,14,15,16,17 },
		{ 18,19,20,21,22,23,24,25,26 },
		{ 27,28,29,30,31,32,33,34,35 },
		{ 36,37,38,39,40,41,42,43,44 },
		{ 45,46,47,48,49,50,51,52,53 }
	},
	{
		{ 57,58,59,60,61,62,54,55,56 },
		{ 66,67,68,69,70,71,63,64,65 },
		{ 75,76,77,78,79,80,72,73,74 },
		{  3, 4, 5, 6, 7, 8, 0, 1, 2 },
		{ 12,13,14,15,16,17, 9,10,11 },
		{ 21,22,23,24,25,26,18,19,20 },
		{ 30,31,32,33,34,35,27,28,29 },
		{ 39,40,41,42,43,44,36,37,38 },
		{ 48,49,50,51,52,53,45,46,47 }
	},
	{
		{ 60,61,62,54,55,56,57,58,59 },
		{ 69,70,71,63,64,65,66,67,68 },
		{ 78,79,80,72,73,74,75,76,77 },
		{  6, 7, 8, 0, 1, 2, 3, 4, 5 },
		{ 15,16,17, 9,10,11,12,13,14 },
		{ 24,25,26,18,19,20,21,22,23 },
		{ 33,34,35,27,28,29,30,31,32 },
		{ 42,43,44,36,37,38,39,40,41 },
		{ 51,52,53,45,46,47,48,49,50 }
	},
	{
		{  0, 9,18,27,36,45,54,63,72 },
		{  1,10,19,28,37,46,55,64,73 },
		{  2,11,20,29,38,47,56,65,74 },
		{  3,12,21,30,39,48,57,66,75 },
		{  4,13,22,31,40,49,58,67,76 },
		{  5,14,23,32,41,50,59,68,77 },
		{  6,15,24,33,42,51,60,69,78 },
		{  7,16,25,34,43,52,61,70,79 },
		{  8,17,26,35,44,53,62,71,80 }
	},
	{
		{ 27,36,45,54,63,72, 0, 9,18 },
		{ 28,37,46,55,64,73, 1,10,19 },
		{ 29,38,47,56,65,74, 2,11,20 },
		{ 30,39,48,57,66,75, 3,12,21 },
		{ 31,40,49,58,67,76, 4,13,22 },
		{ 32,41,50,59,68,77, 5,14,23 },
		{ 33,42,51,60,69,78, 6,15,24 },
		{ 34,43,52,61,70,79, 7,16,25 },
		{ 35,44,53,62,71,80, 8,17,26 }
	},
	{
		{ 54,63,72, 0, 9,18,27,36,45 },
		{ 55,64,73, 1,10,19,28,37,46 },
		{ 56,65,74, 2,11,20,29,38,47 },
		{ 57,66,75, 3,12,21,30,39,48 },
		{ 58,67,76, 4,13,22,31,40,49 },
		{ 59,68,77, 5,14,23,32,41,50 },
		{ 60,69,78, 6,15,24,33,42,51 },
		{ 61,70,79, 7,16,25,34,43,52 },
		{ 62,71,80, 8,17,26,35,44,53 }
	},
	{
		{  3,12,21,30,39,48,57,66,75 },
		{  4,13,22,31,40,49,58,67,76 },
		{  5,14,23,32,41,50,59,68,77 },
		{  6,15,24,33,42,51,60,69,78 },
		{  7,16,25,34,43,52,61,70,79 },
		{  8,17,26,35,44,53,62,71,80 },
		{  0, 9,18,27,36,45,54,63,72 },
		{  1,10,19,28,37,46,55,64,73 },
		{  2,11,20,29,38,47,56,65,74 }
	},
	{
		{ 30,39,48,57,66,75, 3,12,21 },
		{ 31,40,49,58,67,76, 4,13,22 },
		{ 32,41,50,59,68,77, 5,14,23 },
		{ 33,42,51,60,69,78, 6,15,24 },
		{ 34,43,52,61,70,79, 7,16,25 },
		{ 35,44,53,62,71,80, 8,17,26 },
		{ 27,36,45,54,63,72, 0, 9,18 },
		{ 28,37,46,55,64,73, 1,10,19 },
		{ 29,38,47,56,65,74, 2,11,20 }
	},
	{
		{ 57,66,75, 3,12,21,30,39,48 },
		{ 58,67,76, 4,13,22,31,40,49 },
		{ 59,68,77, 5,14,23,32,41,50 },
		{ 60,69,78, 6,15,24,33,42,51 },
		{ 61,70,79, 7,16,25,34,43,52 },
		{ 62,71,80, 8,17,26,35,44,53 },
		{ 54,63,72, 0, 9,18,27,36,45 },
		{ 55,64,73, 1,10,19,28,37,46 },
		{ 56,65,74, 2,11,20,29,38,47 }
	},
	{
		{  6,15,24,33,42,51,60,69,78 },
		{  7,16,25,34,43,52,61,70,79 },
		{  8,17,26,35,44,53,62,71,80 },
		{  0, 9,18,27,36,45,54,63,72 },
		{  1,10,19,28,37,46,55,64,73 },
		{  2,11,20,29,38,47,56,65,74 },
		{  3,12,21,30,39,48,57,66,75 },
		{  4,13,22,31,40,49,58,67,76 },
		{  5,14,23,32,41,50,59,68,77 }
	},
	{
		{ 33,42,51,60,69,78, 6,15,24 },
		{ 34,43,52,61,70,79, 7,16,25 },
		{ 35,44,53,62,71,80, 8,17,26 },
		{ 27,36,45,54,63,72, 0, 9,18 },
		{ 28,37,46,55,64,73, 1,10,19 },
		{ 29,38,47,56,65,74, 2,11,20 },
		{ 30,39,48,57,66,75, 3,12,21 },
		{ 31,40,49,58,67,76, 4,13,22 },
		{ 32,41,50,59,68,77, 5,14,23 }
	},
	{
		{ 60,69,78, 6,15,24,33,42,51 },
		{ 61,70,79, 7,16,25,34,43,52 },
		{ 62,71,80, 8,17,26,35,44,53 },
		{ 54,63,72, 0, 9,18,27,36,45 },
		{ 55,64,73, 1,10,19,28,37,46 },
		{ 56,65,74, 2,11,20,29,38,47 },
		{ 57,66,75, 3,12,21,30,39,48 },
		{ 58,67,76, 4,13,22,31,40,49 },
		{ 59,68,77, 5,14,23,32,41,50 }
	}};
 
byte	tperm[6][3]=	{  
	{ 0, 1, 2 },{ 0, 2, 1 },{ 1, 0, 2 },
	{ 1, 2, 0 },{ 2, 0, 1 },{ 2, 1, 0 }	};

byte	tpart[9][5]=	{ 
	{ 0, 0, 0, 0, 0 },{ 0, 0, 0, 0, 0 },{ 0, 0, 0, 0, 0 },
	{ 4, 5, 6, 7, 8 },{ 3, 5, 6, 7, 8 },{ 3, 4, 6, 7, 8 },
	{ 7, 8, 3, 4, 5 },{ 6, 8, 3, 4, 5 },{ 6, 7, 3, 4, 5 }	};

byte	tboxOffset[9]=	{ 0, 0, 0, 3, 3, 3, 6, 6, 6	};

Canon_t BestInit={
	0,0, // aut box
	{10,10,10,10,10,10,10,10,10,10}, // map
	{0,1,2,3,4,5,6,7,8}, // rows
	{0,1,2,3,4,5,6,7,8}  // cols
};

Canon_t TestInit={
	0,0, // aut box
	{0,0,0,0,0,0,0,0,0,0}, // map
	{0,0,0,0,0,0,0,0,0}, // rows
	{0,0,0,0,0,0,0,0,0}  // cols
};







Canon_t				test,best;

//void GenOut(Canon_t	& ca , unsigned char * inb ){
//	char 	 out[28], *s=out;
//	for (int i = 0; i < 3; i++)
//		for (int j = 0; j < 9; j++)
//			*s++ = ca.map[inb[tswap[ca.box][ca.row[i]][ca.col[j]]]] + '0';
//	out[27]=0;  
//	cout << out;
//}

// quick process without row permutation

void  canon3(unsigned char* sol){
	register int b, d, i, j, k, l, v;
	int		 pr,pc;
	byte *tc=test.col,* tr=test.row,*br=best.row,*bc=best.col,*tmap=test.map,*bmap=best.map;
	// initialize the worst canonical candidate 
	best=BestInit;
	/* search over all boxes */
	for (b = 0; b < 3; b++) {
		for (pr = 0; pr < 6; pr++)
			for (pc = 0; pc < 6; pc++) {
				//if(b==0 && pr==2 && pc==0) diag=1;
				test=TestInit;
				test.box = b;
				/* initialize the map to perm and lock 5 first digits 3 + 2*/
				for (i = 0; i < 3; i++) {
					tr[i] = tperm[pr][i];
					tc[i] = tperm[pc][i];
				}
				const unsigned char * sw0=tswap[b][tr[0]],
					                * sw1=tswap[b][tr[1]],
									* sw2=tswap[b][tr[2]],
									* bw1=tswap[best.box][br[1]],
									* bw2=tswap[best.box][br[2]];
				tmap[ sol [sw0 [ tc[0]] ] ] = 1;
				tmap[ sol [sw0 [ tc[1]] ] ] = 2;
				tmap[ sol [sw0 [ tc[2]] ] ] = 3;
				tmap[ sol [sw1 [ tc[0]] ] ] = 4;
				tmap[ sol [sw1 [ tc[1]] ] ] = 5;				
				k = 0; // map value 6 and order cols 4&5&6 
				for (i = 3; i < 9; i++) {
					if (tmap[sol[sw0 [i]]] == 4) { // find box 2 fitting with locked digits
						l = tboxOffset[i];
						for (j = 0; j < 3; j++)
							switch (tmap[sol[sw0 [j+l]]]) {
							case 4:	tc[3] = j+l;	k |= 01;	break;
							case 5:	tc[4] = j+l;	k |= 02;	break;
							case 0:
								tmap[ sol [sw0[ tc[5]=j+l ] ] ] = 6;
													k |= 04;		break;
						}
						break;
					}
				}
				if (k != 7)		goto next; // box 2 does not fit
				/* map values 7&8&9  from row 1 */
				for (j = 2; j < 6; j++) {
					if (!tmap[sol[sw1[tc[j]]]])  // filter box 3
						tmap[sol[sw1[tc[j]]]] = k++;
				}
		/* check row 2 cols 3&4&5&6 */
				for (j = 2; j < 6; j++) {
					if ((d = (int)tmap[sol[sw1[tc[j]]]]
					       - (int)bmap[sol[bw1[bc[j]]]])) {
						if (d > 0)			goto next;
						break;
					}
				}
				/* order cols 7&8&9 */
				j = (l == 3) ? 6 : 3;		k = j+1; 	l = j+2;
				if (tmap[sol[sw0[j]]]   > tmap[sol[sw0[k]]]) {
					v = j; j = k; k = v;
				}
				if (tmap[sol[sw0[j]]] 	> tmap[sol[sw0[l]]]) {
					v = j; j = l; l = v;
				}
				if (tmap[sol[sw0[k]]]   > tmap[sol[sw0[l]]]) {
					v = k; k = l; l = v;
				}
				tc[6] = j;		tc[7] = k;	tc[8] = l;
				if(d) goto smaller; // already smaller				
				for (j = 6; j < 9; j++) {// check row 2 cols 7&8&9 
					if ((d = (int)tmap[sol[sw1[tc[j]]]] 
					       - (int)bmap[sol[bw1[bc[j]]]])) 
						if (d > 0)	goto next; else goto smaller;						
				}
				for (j = 0; j < 9; j++) {// check row 3 
					if ((d = (int)tmap[sol[sw2[tc[j]]]] 
					       - (int)bmap[sol[bw2[bc[j]]]])) 
						if (d > 0)	goto next; else goto smaller;
				}
				if(!d) goto next; // forget auto morph count
smaller:		best = test;
next:	;// empty next
			}
	}
}

void rowminlex3_1_9(char *in, char *out) {// string in string out
	byte inb[27];
	for(int i=0;i<27;i++) {
		inb[i]=(in[i] & 15)-1; // skip to int mode 0 8
	}
	canon3((unsigned char*)inb);
	register int	i,j;
	register char*	s = out;
	byte * cc=best.col;
	for (i = 0; i < 3; i++)
		for (j = 0; j < 9; j++)
			*s++ = best.map[inb[tswap[best.box][best.row[i]][cc[j]]]] + '0';
	out[27]=0; // normally set by the calling program
}
